package 中等.贪心思想;

/**
 * 给你一个字符串 s 和一个整数 repeatLimit ，用 s 中的字符构
 * 造一个新字符串 repeatLimitedString ，使任何字母 连续 出现
 * 的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
 * 返回 字典序最大的 repeatLimitedString 。
 * <p>
 * 如果在字符串 a 和 b 不同的第一个位置，字符串 a 中的字母在字
 * 母表中出现时间比字符串 b 对应的字母晚，则认为字符串 a 比字符串
 * b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符
 * 都相同，那么较长的字符串字典序更大。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-string-with-repeat-limit
 */
public class 构造限制重复的字符串_6014 {

    public static void main(String[] args) {

        String str = "robnsdvpuxbapuqgopqvxdrchivlifeepy";
        System.out.println(repeatLimitedString(str, 2));
        //yxxvvavuusrrqqpp
        //yxxvvuvusrrqqppopponliihgfeeddcbba

    }

    /**
     * 虽然当某个字符大于1时，可以分类讨论，连续添加<=repeatLimit的字符个数
     * 思路：
     * 每一次遍历，只添加1个字典序最大的字符，如果超出限制，添加字典序第二大的字符
     * <p>
     * 超时！！！
     */
    public static String repeatLimitedString(String s, int repeatLimit) {
        StringBuilder builder = new StringBuilder();
        int[] total = new int[26];
        for (int i = 0; i < s.length(); i++) {  //统计字符个数
            total[s.charAt(i) - 'a']++;
        }
        while (true) {
            for (int i = 25; i >= 0; i--) {
                if (i == 0 && total[0] == 0) {
                    return builder.toString();
                }
                if (total[i] == 0) continue;
                if (isLimit(builder, (char) (i + 'a'), repeatLimit)) {  //超出限制
                    if (i == 0) return builder.toString();  //a超出限制那么不再有比a小字典序的字符
                    for (int pre = i - 1; pre >= 0; pre--) {  //优先使用字典序大的字符
                        if (total[pre] > 0) {
                            builder.append((char) (pre + 'a'));
                            total[pre]--;
                            break;
                        }
                        if (pre == 0) return builder.toString();  //没有找到小一些的字符
                    }
                }
                builder.append((char) (i + 'a'));
                total[i]--;
                i = 26;  //新的遍历从z开始
            }
        }
    }

    public static boolean isLimit(StringBuilder builder, char ch, int limit) {
        if (builder.length() < limit) {
            return false;
        }
        if (builder.length() >= limit) {
            for (int i = builder.length() - 1; i >= 0 && limit > 0; i--) {
                limit--;
                if (builder.charAt(i) != ch) {
                    return false;
                }
            }
        }
        return true;
    }

    //TODO  待优化

}
